The dominating set problem is a core NP-hard problem in combinatorial\r\noptimization and graph theory, and has many important applications. Baker [JACM41,1994]\r\nintroduces a k-outer planar graph decomposition-based framework for designing polynomial\r\ntime approximation scheme (PTAS) for a class of NP-hard problems in planar graphs. It is\r\nmentioned that the framework can be applied to obtain an O(2ckn) time, c is a constant,\r\n(1+1/k)-approximation algorithm for the planar dominating set problem. We show that the\r\napproximation ratio achieved by the mentioned application of the framework is not bounded\r\nby any constant for the planar dominating set problem. We modify the application of the\r\nframework to give a PTAS for the planar dominating set problem. With k-outer planar graph\r\ndecompositions, the modified PTAS has an approximation ratio (1 + 2/k). Using 2k-outer\r\nplanar graph decompositions, the modified PTAS achieves the approximation ratio (1+1/k)\r\nin O(22ckn) time. We report a computational study on the modified PTAS. Our results show\r\nthat the modified PTAS is practical.
Loading....